package num31;

import java.util.Arrays;

/**
 * 31. 下一个排列
 *
 * 题目：https://leetcode-cn.com/problems/next-permutation/
 * 三叶姐题解: https://leetcode-cn.com/problems/next-permutation/solution/miao-dong-xi-lie-100-cong-xia-yi-ge-pai-gog8j/
 */
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int k = n - 1;
        while (k - 1 >= 0 && nums[k - 1] >= nums[k]) {
            k--;
        }
        if (k == 0) {
            reverse(nums, 0, n - 1);
        } else {
            int u = k;
            while (u + 1 < n && nums[u + 1] > nums[k - 1]) {
                u++;
            }
            swap(nums, k - 1, u);
            reverse(nums, k, n - 1);
        }
    }

    void reverse(int[] nums, int a, int b) {
        int l = a, r = b;
        while (l < r) {
            swap(nums, l++, r--);
        }
    }

    void swap(int[] nums, int a, int b) {
        int c = nums[a];
        nums[a] = nums[b];
        nums[b] = c;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 5, 4, 1};
        new Solution().nextPermutation(arr);
        System.out.println(Arrays.toString(arr));

    }
}